#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define all(x) (x).begin(),(x).end()
typedef long long ll;

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<VI> VVI;

typedef pair<int, int> PII;
typedef vector<PII> VPII;
#define X first
#define Y second
#define mp make_pair

#define two(x) (1<<(x))
#define twoll(x) ((long long)1<<(x))
#define contain(s,x) (((s)&two(x))!=0)
#define containll(s,x) (((s)&twoll(x))!=0)

#define db(a) cout << #a << "=" << a << " "
#define dbn cout << endl
template<class T> void print(vector<T> v) { cout << "["; if (v.size()) cout << v[0]; for (unsigned i = 1; i < v.size(); i++) cout << ", " << v[i];cout << "]\n"; }
template<class T> void print(vector<vector<T> > v) { cout << "[ ---\n"; if (v.size()) cout << " ", print(v[0]); for (unsigned i = 1; i < v.size(); i++) cout << " ", print(v[i]); cout << "--- ]\n"; }
template<class T1, class T2> void print(pair<T1, T2> p) { cout << "{" << p.first << ", " << p.second << "}"; }
template<class T1, class T2> void print(vector<pair<T1, T2> > v) { cout << "["; if (v.size()) print(v[0]); for (unsigned i = 1; i < v.size(); i++) cout << ", ", print(v[i]);cout << "]\n"; }
template<class T> inline T sqr(T x) { return x*x; }

template<class T> inline int chkmin(T& a, T b) { if (a>b) {a=b; return 1;} return 0; }
template<class T> inline int chkmax(T& a, T b) { if (a<b) {a=b; return 1;} return 0; }

string STR(int n) { char tmp[20]; sprintf(tmp,"%d",n); return tmp; }
int INT(string s) { return atoi(s.c_str()); }
template <class Ty, class Tx> Ty to(const Tx &x) { Ty y; stringstream ss; ss<<x; ss>>y; return y; }

const int INF = 1000000007;
const double EPS = 1e-10;

char buf[1<<20];

int CUR_CASE;
int TOTAL_CASES;

int N,M,B,L;

int G[101][101];
vector<pair<int,pair<int,int> > > C;
VPII VC;
int dp[105];

int main() {
#define SUBMIT 0
#if !SUBMIT
	freopen("DATA.in", "rt", stdin);
	freopen("DATA.ou", "wt", stdout);
	clock_t STARTTIME, ENDTIME;
	STARTTIME = clock();
#endif

	gets(buf);
	TOTAL_CASES = atoi(buf);
	
	for (CUR_CASE = 1; CUR_CASE <= TOTAL_CASES; ++CUR_CASE)
	{
		memset(dp,0,sizeof(dp));
		VC.clear();
		C.clear();
#define index first
#define demand second.first
#define priority second.second
		scanf("%d",&N);
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < N; ++j)
				if (i == j)
					G[i][j] = 0;
				else
					G[i][j] = INF;
		scanf("%d",&M);
		for (int i = 0; i < M; ++i)
		{
			int idx,d,p;
			scanf("%d%d%d",&idx,&d,&p);
			C.push_back(mp(idx,mp(d,p)));
		}
		scanf("%d",&B);
		scanf("%d",&L);
		for (int i = 0; i < L; ++i)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			G[a][b] = c;
		}
		
		for (int k = 0; k < N; ++k)
			for (int i = 0; i < N; ++i)
				for (int j = 0; j < N; ++j)
					G[i][j] = min(G[i][j],G[i][k]+G[k][j]);
		for (int i = 0; i < C.size(); ++i)
		{
			int idx = C[i].index;
			int d = C[i].demand;
			int p = C[i].priority;
			if ((ll)G[0][idx]*d <= B)
				VC.push_back(mp(p,G[0][idx]*d));
		}
		for (int i = 0; i < VC.size(); ++i)
		{
			int c = VC[i].Y;
			int v = VC[i].X;
			for (int j = B-c; j >= 0; --j)
				dp[j+c] = max(dp[j+c],dp[j]+v);
		}
		int res = *max_element(dp,dp+B);
		printf("%d\n",res);
	}

#if !SUBMIT
	ENDTIME = clock();
	cerr << "elapsed time : " << ENDTIME-STARTTIME << "ms";
#endif
	return 0;
}





